package test;

//制作m朵花的最少天数：https://leetcode.cn/problems/minimum-number-of-days-to-make-m-bouquets/
//时间复杂度：O(n*log(max))
public class MinDays {
	 //f: limit天内能否制作m朵花
    public boolean f(int[] bloomDay,int m,int k,int limit){
    	//滑窗： 窗口大小为k
        for(int l=0,r=0;r<bloomDay.length;r++){
            if(bloomDay[r]>limit){
                l=r+1;
                continue;
            }
            //窗口正好为k时，表示制作成功了一朵花
            if(r-l+1==k){
                m--;
                l=r+1;
            }
            if(m==0){
                return true;
            }
        }
        return false;
    }
    public int minDays(int[] bloomDay, int m, int k) {
    	//m<=10^6，因此m*k极有可能溢出，因此转为long
        if((long)m*k>bloomDay.length) return -1;
        int max=-1;
        for(int x:bloomDay) {
            max=Math.max(max,x);
        }
        //二分区间[0,max]
        int l=1,r=max,ret=0;
        while(l<=r){
            int mid=l+(r-l)/2;
            if(f(bloomDay,m,k,mid)==true){
                ret=mid;
                r=mid-1;
            }
            else{
                l=mid+1;
            }
        }
        return ret;
    }
}
